package com.zjj.lbw.interview.greedy;

import java.util.*;

/**
 * @author zhanglei.zjj
 * @description 优势洗牌（田忌赛马）
 *  给定两个大小相等的数组 A 和 B，A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。
 *  返回 A 的任意排列，使其相对于 B 的优势最大化。
 * @date 2023/9/16 10:19
 */
public class HorseRacing {
    public static int[] advantageCount(int[] A, int[] B) {
        int[] bClone = B.clone();
        Arrays.sort(bClone);
        Arrays.sort(A);

        Map<Integer, LinkedList<Integer>> map = new HashMap<>(bClone.length);
        for (int i : bClone) {
            map.put(i, new LinkedList<>());
        }
        int index = 0;
        Deque<Integer> queue = new LinkedList<>();

        for (int i = 0; i < A.length; i++) {
            if (A[i] > bClone[index]) {
                map.get(bClone[index++]).add(A[i]);
            } else {
                queue.offer(A[i]);
            }
        }

        int[] resultA = new int[A.length];
        for (int i = 0; i < B.length; i++) {
            if (!map.get(B[i]).isEmpty()) {
                resultA[i] = map.get(B[i]).removeLast();
            } else {
                resultA[i] = queue.poll();
            }
        }

        return resultA;

    }

    public static void main(String[] args) {
        int[] A = new int[]{10, 24, 8, 32};
        int[] B = new int[]{13, 25, 25, 11};
        System.out.println(Arrays.toString(advantageCount(A, B)));
    }
}
